package mashibing.class21;

/**
 * arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * 每个值都认为是一种面值，且认为张数是无限的。
 * 返回组成aim的方法数
 * 例如：arr = {1,2}，aim = 4
 * 方法如下：1+1+1+1、1+1+2、2+2
 * 一共就3种方法，所以返回3
 */
public class Class21_3_CoinsWayNoLimit {

    // 1、递归
    public static int coinsWay1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process(arr, 0, aim);
    }

    private static int process(int[] arr, int index, int rest) {
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        // 张数和张的值乘积小于剩余的余额
        int way = 0;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            way += process(arr, index + 1, rest - zhang * arr[index]);
        }
        return way;
    }

    // 2、dp
    public static int coinsWay2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        dp[arr.length][0] = 1;
        for (int index = arr.length - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int way = 0;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                    way += dp[index + 1][rest - zhang * arr[index]];
                }
                dp[index][rest] = way;
            }
        }
        return dp[0][aim];
    }

    // 3、dp优化
    public static int coinsWay3(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        dp[arr.length][0] = 1;
        for (int index = arr.length - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int way = dp[index + 1][rest];
                if (rest - arr[index] >= 0) {
                    way += dp[index][rest - arr[index]];
                }
                dp[index][rest] = way;
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {
        int[] arr = {21, 30, 10, 3, 15, 17};
        int aim = 15;
        System.out.println(coinsWay1(arr, aim));     // 2
        System.out.println(coinsWay2(arr, aim));     // 2
        System.out.println(coinsWay3(arr, aim));     // 2
    }
}
